国防科技大学 编译原理 第3讲 高级程序设计语言的语法描述

课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

这次回顾第3讲：高级程序设计语言的语法描述。

第3讲 高级程序设计语言的语法描述

文法

• 文法：描述语言的语法结构的形式规则

• 假设我们有如下文法：

• ```
  <句子> -> <主语><谓语><间接宾语><直接宾语>
  <主语> -> <代词>
  <谓语> -> <动词>
  <间接宾语> -> <代词>
  <直接宾语> -> <冠词> <名词>
  <代词> -> He
  <代词> -> me
  <名词> -> book
  <冠词> -> a
  <动词> -> gave

  
  - 考虑句子：He gave me a book.
  
  - ```
      <句子>
    =><主语><谓语><间接宾语><直接宾语>
    =><代词><谓语><间接宾语><直接宾语>
    =>He <谓语><间接宾语><直接宾语>
    =>He <动词> <间接宾语><直接宾语>
    =>He gave <间接宾语><直接宾语>
    =>He gave <代词> <直接宾语>
    =>He gave me <直接宾语>
    =>He gave me <冠词><名词>
    =>He gave me a <名词>
    =>He gave me a book

语法描述的几个基本概念

• 字母表：一个有穷字符集，记为$\Sigma$

• 字母表中每个元素称为字符

• $\Sigma$上的字(也叫字符串) 是指由$\Sigma$中的字符所构成的一个有穷序列

• 不包含任何字符的序列称为空字，记为$\varepsilon$

• 用$\Sigma^{\star}$表示$\Sigma$上的所有字的全体，包含空字$\varepsilon$

  • 例如: 设 $\Sigma=\{a,b\}$，则

$$\Sigma^{\star}=\{\varepsilon ,a,b,aa,ab,ba,bb,aaa,\ldots\}$$

• $\Sigma^{\star}$的子集$U$和$V$的连接（积）定义为

  $$UV＝\{ \alpha\beta | \alpha \in U \& \beta\in V \}$$

• 示例：$U=\{a,aa\},V=\{b,bb\},UV=\{ab,abb,aab,aabb\}$

• $V$自身的$n$次积记为

  $$V^n=\underbrace{V\ldots V}_{n个}$$

• $V^0=\{\varepsilon\}$

• $V^{\star}$是$V$的闭包：$V^\star =V^0\cup V^1\cup V^2\ldots$

• $V^{+}$是$V$的正规闭包：$V^+=VV^\star $

  • 例子：

    $$U=\{a,aa\}$$

  • 那么：

    $$\begin{aligned} U^{\star}&=\{\varepsilon, a,aa,aaa,aaaa,\ldots\}\\ U^{+}&=\{a,aa,aaa,aaaa,\ldots\} \end{aligned}$$

上下文无关文法

• 上下文无关文法$G$是一个四元组

  $$G=(V_T,V_N,S,P)$$

• 其中

  • $V_T$：终结符(Terminal)集合(非空)
  • $V_N$：非终结符(Noterminal)集合(非空)，且$V_T \cap V_N=\varnothing$
  • $S$：文法的开始符号，$S\in V_N$
  • $P$：产生式集合(有限)，每个产生式形式为
    • $P\to \alpha， P\in V_N， \alpha∈ (V_T \cup V_N)^{\star}$
  • 开始符$S$至少必须在某个产生式的左部出现一次

• 上下文无关文法还有一种描述形式，称为巴科斯范式(BNF)

  • “ →”用“::=”表示

例子

定义只含$+，\star$的算术表达式的文法

$$G=< \{i,+,\star,(,)\}，\{E\},E,P >$$

其中，$P$的定义如下：

• $E → i$
• $E → E+E$
• $E → E\star E$
• $E → (E)$

一些约定

• 约定

  $$\begin{array}{l} P \rightarrow \alpha_{1} \\ P \rightarrow \alpha_{2} \quad \overset {\text { 可缩写为 }}{\Rightarrow} \\ \ldots \\ {P} \rightarrow \alpha_{\mathrm{n}} \end{array} P \rightarrow \alpha_{1}\left|\alpha_{2}\right| \ldots \mid \alpha_{\mathrm{n}}$$

• 其中，“$|$”读成“或”，称$α_i$为$P$的一个候选式

  • 表示一个文法时，通常只给出开始符号和产生式

• 之前的文法可以简写为

  $$G(E)： E → i | E+E | E\star E | (E)$$

文法生成语言

推导

• 定义：称$αAβ$直接推出$αγβ$，即

  $$αAβ\Rightarrow \alphaγβ$$

  仅当$A → γ$是一个产生式，且$\alpha,β∈ (V_T \cup V_N)^{\star}$。

• 如果$α_1 \Rightarrow α_2 \Rightarrow\ldots \Rightarrow α_n$，则我们称这个序列是从$α_1$到$α_n$的一个推导。若存在一个从$α_1$到$α_n$的推导，则称$α_1$可以推导出$α_n$。

• 对文法$G(E)： E → i | E+E | E\star E | (E)$

  $$E\Rightarrow (E)\Rightarrow (E+E)\Rightarrow (i+E)\Rightarrow (i+i)$$

• $\alpha_1 \overset{\star}\Rightarrow \alpha_n$：从$α_1$出发，经过$0$步或若干步推出$α_n$

• $\alpha_1 \overset{+}\Rightarrow \alpha_n$：从$α_1$出发，经过$1$步或若干步推出$α_n$

• $\alpha ⇒ 𝛽$ ：即$𝛼 = 𝛽$或$\alpha \overset{+}\Rightarrow \beta$

  • <句子> $ \overset{\star}\Rightarrow$ He gave me a book
  • <句子> $ \overset{+}\Rightarrow$ He gave me a book
  • He gave <间接宾语><直接宾语>$ \overset{+}\Rightarrow$He gave me <冠词> <名词>

之前例子的推导过程：

句型、句子和语言

• 假定$G$是一个文法，$S$是它的开始符号。

• 如果$S \overset{\star}\Rightarrow \alpha$，则称$α$是一个句型。

• 仅含终结符号的句型是一个句子。

• 文法$G$所产生的句子的全体是一个语言，记为$L(G)$:

  $$L(G)=\{\alpha | S\overset{+}\Rightarrow \alpha, \alpha\in V_T^{\star}\}$$

例子

证明$(i \star i+i)$是文法

$$G(E)： E → i | E+E | E\star E | (E)$$

的一个句子。

证明：

$$\begin{aligned} E & \Rightarrow(E) \\ & \Rightarrow(E+E) \\ & \Rightarrow\left(E{\star} E+E\right) \\ & \Rightarrow\left(i{\star} E+E\right) \\ & \Rightarrow\left(i{\star} i+E\right) \\ & \Rightarrow\left(i{\star} i+i\right) \end{aligned}$$

所以$(i+i)$是文法$G$的句子，$E,(E),(E\star E+E),\ldots, (i\star i+i)$是句型。

从文法到语言

例1

• 设文法 $$G_1(A)： A → c | Ab$$

• $G_1(A)$产生的语言是什么?

  • 以$c$开头，后继若干个$b$

    $$L(G_1)=\{c,cb,cbb,\ldots \}$$
  • $$\begin{aligned} {A} & \Rightarrow {c} \\ {A} & \Rightarrow {Ab} \\ & \Rightarrow {cb} \\ {A} & \Rightarrow {Ab} \\ & \Rightarrow {Abb} \\ & \Rightarrow {Abbb} \\ & \Rightarrow \ldots \\ & \Rightarrow {Ab} \ldots {b} \\ & \Rightarrow {cb} \ldots {b} \end{aligned}$$

例2

• 设文法

  $$\begin{aligned} G_2(S): &S \to AB\\ &A \to aA|a\\ &B \to bB|b \end{aligned}$$

• $G_2(S)$产生的语言是什么?

  $$L(G_2)=\{a^mb^n|m,n>0\}$$
• $$\begin{aligned} S & \Rightarrow A B \\ A & \Rightarrow a \\ A & \Rightarrow a A \\ & \Rightarrow a a A \\ & \Rightarrow a a a A \\ & \Rightarrow \ldots \\ & \Rightarrow a \ldots a A \\ & \Rightarrow a \ldots a a \\ B & \Rightarrow b \\ B & \Rightarrow b B \\ & \Rightarrow b b B \\ & \Rightarrow b b b B \\ & \Rightarrow \ldots \\ & \Rightarrow b \ldots b B\\ & \Rightarrow b \ldots bb \end{aligned}$$

例3

请给出产生语言为$\{a^nb^n|n≥1\}$的文法

$$\begin{aligned} G_3(S):& S\to aSb\\ &S\to ab \end{aligned}$$

例4

请给出产生语言为$\{a^mb^n|1≤n≤m≤2n\}$的文法

$$\begin{aligned} G_4(S):& S\to ab | aab\\ &S → aSb | aaSb \end{aligned}$$

推导与语法树

最左推导和最右推导

• 从一个句型到另一个句型的推导往往不唯一

  $$\begin{aligned} E+E&\Rightarrow i+E\Rightarrow i +i\\ E+E&\Rightarrow E+i\Rightarrow i +i \end{aligned}$$

• 最左推导：任何一步$\alpha \Rightarrow \beta$都是对$α$中的最左非终结符进行替换

• 最右推导：任何一步$\alpha \Rightarrow \beta$都是对$α$中的最右非终结符进行替换

语法树

• 用一张图表示一个句型的推导，称为语法树
• 一棵语法树是不同推导过程的共性抽象

语法树与二义性(ambiguity)

• 一个句型是否只对应唯一一棵语法树？考虑如下例子：

• $G(E)： E → i | E+E | E\star E | (E)$是二义的(ambiguous)

• $(i\star i+i)$对应了两棵语法树

  

具体定义：

• 文法的二义性：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的

  • 例如$G(E)： E → i | E+E | E\star E | (E)$

  • 可以将其改写为无二义文法$G’(E)$：

    

• 语言的二义性：一个语言是二义的，如果对它不存在无二义的文法

  • 对于语言$L$，可能存在$G$和$G’$，使得$L(G)=L(G’)=L$，有可能其中一个文法为二义的， 另一个为无二义的
  • 例如John saw Mary in a boat.是二义的，因为in a boat可以修饰Mary或者John。

• 二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的

• 但可以找到一组无二义文法的充分条件

形式语言鸟瞰

• 乔姆斯基(Chomsky)是美国当代有重大影响的语言学家

• 乔姆斯基于1956年建立形式语言体系，他把文法分成四种类型：$0,1,2,3$型

• 与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同

  • $G=(V_T，V_N，S，P)$

    • $V_T$：终结符(Terminal)集合(非空)

    • $V_N$：非终结符(Noterminal)集合(非空)，且$V_T \cap V_N=\varnothing$

    • $S$：文法的开始符号，$S\in V_N$

    • $P$：产生式集合(有限)

四种文法分别如下：

• 0型(短语文法，图灵机)
  • 产生式形如：$α → β$
  • 其中：$\alpha\in (V_T ∪ V_N)^{\star}$且至少含有一个非终结符；$\beta\in (V_T ∪ V_N)^{\star}$
• 1型(上下文有关文法，线性界限自动机)
  • 产生式形如：$α → β$
  • 其中：$|α| \le |β|$，仅$S→\varepsilon $例外
• 2型(上下文无关文法，非确定下推自动机)
  • 产生式形如： $A → β$
  • 其中：$A∈ V_N；β∈ (V_T \cup V_N)^\star$
• 3型(正规文法，有限自动机)
  • 产生式形如：$A → αB$或$A → α$
    • 其中：$α∈ V_T^{\star};A,B∈V_N$（右线性文法）
  • 产生式形如：$A → Bα$或$A → α$
    • 其中：$α∈ V_T^{\star};A,B∈V_N$（左线性文法）

四种类型文法描述能力比较

上下文无关文法与上下文有关文法

例1

$L_5 =\{a^nb^n|n≥1\}$不能由正规文法(3型)产生，但可由上下文无关文法产生

$$G_5(S)： S → aSb| ab$$

例2

$L_6=\{a^n b^nc ^n|n≥1\}$不能由上下文无关文法产生，但可由上下文有关文法产生

$$\begin{aligned} G_6(S): &S \to aSBC| aBC\\ &CB → BC\\ &aB → ab\\ &bB → bb\\ &bC → bc\\ &cC → cc \end{aligned}$$

推导例子：

$$\begin{aligned} &S\\ \Rightarrow & aSBC\\ \Rightarrow & aaSBCBC\\ \Rightarrow & aaaBCBCBC\\ \Rightarrow & aaaBBCCBC\\ \Rightarrow & aaaBBCBCC\\ \Rightarrow & aaaBBBCCC\\ \Rightarrow & aaabBBCCC\\ \Rightarrow & aaabbBCCC\\ \Rightarrow & aaabbbCCC\\ \Rightarrow & aaabbbcCC\\ \Rightarrow & aaabbbccC\\ \Rightarrow & aaabbbccc \end{aligned}$$

小结

• 程序设计语言不是上下文无关语言，甚至不是上下文有关语言
• $L_7=\{αcα| α∈\{a,b\}^\star \}$不能由上下文无关文法产生，甚至连上下文有关文法也不能产生，只能由$0$型文法产生
  • $L_7$对应了
    • 标识符引用
    • 过程调用过程中，“形-实参数的对应性”(如个数，顺序和类型一致性)
• 对于现今程序设计语言，在编译程序中，仍然采用上下文无关文法来描述其语言结构
  • 这是一种权衡